#include <iostream>
#include <string>
#include <unordered_map>
#include <set>
#include <vector>
#include <ctime>
#include <algorithm>
#include <assert.h>
#include <math.h>

using namespace std;

//服务器结构
struct Server{
	string type;
	int cpuA, cpuB, memA, memB, serverCost, powerCost;
	int rest;
	//空参构造器
	Server(){}
	//带参构造器
	Server(string type, int cpuCore, int memSize, int sCost, int pCost):type(type),serverCost(sCost),powerCost(pCost){
		this->cpuA = cpuCore / 2;
		this->cpuB = this->cpuA;
		this->memA = memSize / 2;
		this->memB = this->memA;
	}
};

//虚拟机结构
struct VirtualMachine{
	string type;
	int cpuCore, memSize, isDual;
	//空参构造器
	VirtualMachine(){}
	//带参构造器
	VirtualMachine(string type, int cpuCore, int memSize, int isDual):type(type),cpuCore(cpuCore),memSize(memSize),isDual(isDual){}
};

//添加请求结构
struct Request{
	string type;//add or del
	string vmType, vmId;
	int vmCpu, vmMem, isDual;
	Request(){}//空参构造器
	Request(string type, string vmType, string vmId, int vmCpu, int vmMem, int isDual):type(type),vmType(vmType),vmId(vmId),vmCpu(vmCpu),vmMem(vmMem),isDual(isDual){}
	//当其为一条删除请求时，只有其vmId有效，其他的数据别访问，会出错。
	Request(string type, string vmId):type(type),vmId(vmId){}
};

/******* 全局变量 ***********************/
unordered_map<string, Server> svInfos;              //原始的服务器信息
unordered_map<string, VirtualMachine> vmInfos;      //原始的虚拟机信息
vector<Server> sortedServers;                       //按价格排序服务器
vector<vector<Request>> daysReqs;                            //每日的请求

vector<Server> svResources;                         //购买的服务器
#define DeployInfo vector<int>                      //虚拟机的部署信息。{服务器编号, 占用cpu, 占用mem, maybe 部署节点}。长度为3->双节点部署;当长度为4->单节点部署（0-A,1->B）
unordered_map<string, DeployInfo> vmDeployInfos;    //记录虚拟机运行在哪台服务器上(key=虚拟机id(不是类型), value={服务器编号,占用cpu,占用mem,部署节点})
vector<vector<string>> svRunVms;                    //记录已购的每台服务器上的各自运行的虚拟机Id。长度和已购服务器的数量对应
//vector<int> svRunVmsNumber;                         //记录已购的每台服务器上的各自运行的虚拟机数量（看似显得多余，其实是为了方便后续的处理）。长度和已购服务器的数量对应
int T;
vector<vector<string>> purchase_info;//每天的购买信息
vector<vector<string>> migrate_info;//每天的迁移信息
vector<vector<string>> deploy_info;//每天的部署信息
//提交时可能用不到的变量
# define INPUT_REDIRECTION_1 "training-data/training-1.txt"  //输入重定向
# define INPUT_REDIRECTION_2 "training-data/training-2.txt"  //输入重定向
# define OUTPUT_REDIRECTION "result.txt"                     //输出重定向
long long SERVERCOST=0, POWERCOST=0, TOTALCOST=0;            //各种成本
long long SC=0, PC=0, TC=0;                                  //两份数据的成本
/************************************************/


/****************** 读数据构建各种类型的 服务器 和 虚拟机 ********************/
void readServer(string &serverType, string &cpuCore, string &memSize, string &serverCost, string &powerCost){
	string _serverType = "";
    for(int i =1; i<serverType.size()-1; i++) _serverType += serverType[i];
    int _cpuCore=0, _memSize=0, _serverCost=0, _powerCost=0;
    for(int i=0; i<cpuCore.size()-1; i++) _cpuCore = 10*_cpuCore + cpuCore[i] - '0';
    for(int i=0; i<memSize.size()-1; i++) _memSize = 10*_memSize + memSize[i] - '0';
    for(int i=0; i<serverCost.size()-1; i++) _serverCost = 10*_serverCost + serverCost[i] - '0';
    for(int i=0; i<powerCost.size()-1; i++) _powerCost = 10*_powerCost + powerCost[i] - '0';
	svInfos[_serverType] = Server{_serverType, _cpuCore, _memSize, _serverCost, _powerCost};
}
void readVm(string &vmType, string &cpuCore, string &memSize, string &isDual){
    string _vmType = "";
    for(int i=1; i<vmType.size()-1; i++) _vmType += vmType[i];
    int _cpuCore=0, _memSize=0, _isDual=0;
    for(int i=0; i<cpuCore.size()-1; i++) _cpuCore = _cpuCore*10 + cpuCore[i] - '0';
    for(int i=0; i<memSize.size()-1; i++) _memSize = _memSize*10 + memSize[i] - '0';
    if(isDual[0] == '1') _isDual = 1;
    vmInfos[_vmType] = VirtualMachine{_vmType, _cpuCore, _memSize, _isDual};
}
//对服务器，按价格排序
bool sv_cmp_serverprice_up (Server const &s1, Server const s2){
	return s1.serverCost < s2.serverCost;
	//return s1.unitPrice < s2.unitPrice;
}
void readServerAndVmInfos(){
	int svNum;//服务器数量
	string type, cpuCore, memSize, serverCost, powerCost, isDual;
	scanf("%d", &svNum);
	for (int i=0; i<svNum; i++){
		cin>>type>>cpuCore>>memSize>>serverCost>>powerCost;
		readServer(type, cpuCore, memSize, serverCost, powerCost);
	}
	int vmNum;//虚拟机数量
    scanf("%d",&vmNum);
	for (int i =0; i<vmNum; i++){
        cin>>type>>cpuCore>>memSize>>isDual;
        readVm(type, cpuCore, memSize, isDual);
    }
    //复制一份排序。
    for(auto const &pair:svInfos) sortedServers.emplace_back(pair.second);
	sort(sortedServers.begin(), sortedServers.end(), sv_cmp_serverprice_up);
}
/*****************************************************************************/

/************** 读数据构建每日请求 ****************/
void readAddRequest(int day, string &op, string & reqVmType, string &reqVmId){
	string _op, _reqVmType, _reqVmId;
    _op = op.substr(1, op.size()-2);
    _reqVmType = reqVmType.substr(0, reqVmType.size()-1);
    _reqVmId = reqVmId.substr(0, reqVmId.size() -1);
    VirtualMachine vm = vmInfos[_reqVmType];
    daysReqs[day].emplace_back(Request{_op, _reqVmType, _reqVmId, vm.cpuCore, vm.memSize, vm.isDual});
}
void readDelRequest(int day, string &op, string &reqVmId){
	string _op, _reqVmId;
    _op = op.substr(1, op.size()-2);
    _reqVmId = reqVmId.substr(0, reqVmId.size()-1);
    daysReqs[day].emplace_back(Request{_op, _reqVmId});
}
void readDayRequests(int day, int dayReqNumber){
	string op, reqVmType, reqVmId;
	daysReqs.emplace_back(vector<Request>{});
	for (int i=0; i<dayReqNumber; i++){
		cin>>op;
		if(op[1] == 'a'){
			cin>>reqVmType>>reqVmId;
			readAddRequest(day, op, reqVmType, reqVmId);;
		}else{
			cin>>reqVmId;
			readDelRequest(day, op, reqVmId);
		}
	}
}
/**************************************************/

//一定能找到一台服务器能装下，所以不用考虑返回值不存在的情况。返回值是服务器在sortedServers中的索引
int buyBestServer(vector<Server> const &servers, Request const &req){
	int needCpu = req.isDual ? req.vmCpu/2 : req.vmCpu;
	int needMem = req.isDual ? req.vmMem/2 : req.vmMem;
	for(int i=0; i<servers.size(); i++){
		//单双节点都是统一的判断方式，很神奇，是吧
		Server const &sv=servers[i];
		if(sv.cpuA>=needCpu && sv.memA>=needMem) return i;
	}
	return -1;//这个地方永远也执行不了
}

//快速排序，按照请求中的虚拟机资源（vmCpu + vmMem）排序
void quickSort_cpumem_down(vector<Request> &reqs, int l, int r){
	if (l < r){
		int i=l, j=r;
		Request req=reqs[l];
		while(i < j){
			while(reqs[j].vmCpu+reqs[j].vmMem < req.vmCpu+req.vmMem && i<j) j--;
			if(i < j) reqs[i++] = reqs[j];
			while(reqs[i].vmCpu+reqs[i].vmMem >= req.vmCpu+req.vmMem && i<j) i++;
			if(i < j) reqs[j--] = reqs[i];
		}
		reqs[i] = req;
		quickSort_cpumem_down(reqs, l, i-1);
		quickSort_cpumem_down(reqs, i+1, r);
	}
}
//分段排序所有请求(cpu+mem)，以删除请求分段
void segmentSort(vector<Request> &reqs){
	int start=0;
	for(int i=0; i<reqs.size(); i++){
		if(reqs[i].type=="del"){
			quickSort_cpumem_down(reqs, start, i-1);
			start=i+1;
		}
	}
}

//虚拟机放在哪台服务器上，能最大限度地填满它，保证已较满的服务器更满。返回所在servers中的索引，找不到就返回-1。并且可以指定从哪个位置开始往后找
int findBestServer(vector<Server> const &servers, Request const &req, int start=0){
	int index = -1;
	int minRest = ~(1<<(sizeof(int)*8 - 1));
	int needCpu = req.isDual ? req.vmCpu/2 : req.vmCpu;
	int	needMem = req.isDual ? req.vmMem/2 : req.vmMem;
	int rest = 0;
	if(req.isDual){//双节点
		for(int i=start; i<servers.size(); i++){
			Server const &sv = servers[i];
			if(sv.cpuA>=needCpu && sv.cpuB>=needCpu && sv.memA>=needMem && sv.memB>=needMem){
				rest = sv.cpuA+sv.cpuB+sv.memA+sv.memB - req.vmCpu - req.vmMem;//放入后的剩余资源量 cpu + mem
				if(rest < minRest){
					index = i;
					minRest=rest;
				}
			}
		}
	}else{//单节点
		for(int i=start; i<servers.size(); i++){
			Server const &sv = servers[i];
			if((sv.cpuA>=needCpu && sv.memA>=needMem) || (sv.cpuB>=needCpu && sv.memB>=needMem)){
				rest = sv.cpuA+sv.cpuB+sv.memA+sv.memB - req.vmCpu - req.vmMem;//放入后的剩余资源量 cpu + mem
				if(rest < minRest){
					index = i;
					minRest=rest;
				}
			}
		}
	}
	return index;
}

//为一波请求买服务器，并同时部署。这波请求可能含有del
void buyServersForReqs(vector<Request> const &reqs){
	int old_sv_number = svResources.size();//新买的服务器从这里开始编号
	unordered_map<string, DeployInfo> temp_dep_infos;//临时的部署信息，最后把这个信息更新到全局部署信息中。这里主要是为了编号映射，太麻烦了
	
	for(Request const &req:reqs){
		string vmId = req.vmId;
		if(req.type=="add"){//添加请求
			int isDual = req.isDual;
			int needCpu = isDual ? req.vmCpu/2 : req.vmCpu;
			int needMem = isDual ? req.vmMem/2 : req.vmMem;
			int svId = findBestServer(svResources, req, old_sv_number);
			if (svId < 0){//需购买
				int index = buyBestServer(sortedServers, req);//找到一台最合适的服务器
				Server sv = sortedServers[index];//购买
				SERVERCOST += sv.serverCost;
				svId = svResources.size();//这台新购买的服务器编号
				if(isDual){//双节点
					sv.cpuA -= needCpu;
					sv.cpuB -= needCpu;
					sv.memA -= needMem;
					sv.memB -= needMem;
					temp_dep_infos[vmId]=DeployInfo{svId, needCpu, needMem};
				}else{//单节点，默认放在新买服务器的B节点上
					sv.cpuB -= needCpu;
					sv.memB -= needMem;
					temp_dep_infos[vmId]=DeployInfo{svId, needCpu, needMem, 1};
				}
				svResources.emplace_back(sv);
				//svRunVmsNumber.emplace_back(1);
				svRunVms.emplace_back(vector<string>{vmId});
			}else{//无需购买即可部署
				Server &sv = svResources[svId];//涉及到修改资源量了
				if(isDual){//双节点部署
					sv.cpuA -= needCpu;
					sv.cpuB -= needCpu;
					sv.memA -= needMem;
					sv.memB -= needMem;
					temp_dep_infos[vmId] = DeployInfo{svId, needCpu, needMem};
					//svRunVmsNumber[svId]++;
					svRunVms[svId].emplace_back(vmId);
				}else{//单节点部署
					if(sv.cpuA >= sv.cpuB){//A节点剩得多
						if(sv.cpuA>=needCpu && sv.memA>=needMem){//并且A节点能放下
							sv.cpuA -= needCpu;
							sv.memA -= needMem;
							temp_dep_infos[vmId] = DeployInfo{svId, needCpu, needMem, 0};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
						if(sv.cpuB>=needCpu && sv.memB>=needMem){//虽然A节点剩得多，但是A节点放不下，那么看B节点能不能放下
							sv.cpuB -= needCpu;
							sv.memB -= needMem;
							temp_dep_infos[vmId] = DeployInfo{svId, needCpu, needMem, 1};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
					}else{//B节点剩得多
						if(sv.cpuB>=needCpu && sv.memB>=needMem){//并且B节点能放下
							sv.cpuB -= needCpu;
							sv.memB -= needMem;
							temp_dep_infos[vmId] = DeployInfo{svId, needCpu, needMem, 1};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
						if(sv.cpuA>=needCpu && sv.memA>=needMem){//虽然B节点剩得多，但是B节点放不下，那么看A节点能不能放下
							sv.cpuA -= needCpu;
							sv.memA -= needMem;
							temp_dep_infos[vmId] = DeployInfo{svId, needCpu, needMem, 0};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
					}
				}
			}
		}else{//删除请求
			DeployInfo vmDeInfo = vmDeployInfos[vmId];
			int svId=vmDeInfo[0], occupiedCpu=vmDeInfo[1], occupiedMem=vmDeInfo[2];//获取部署时的关键信息
			Server &sv=svResources[svId];//涉及到修改资源量了
			if(vmDeInfo.size() == 3){//之前是双节点部署的
				sv.cpuA += occupiedCpu;
				sv.cpuB += occupiedCpu;
				sv.memA += occupiedMem;
				sv.memB += occupiedMem;
			}else{//之前是单节点部署的
				if(vmDeInfo[3] == 0){//之前是部署在A节点上
					sv.cpuA += occupiedCpu;
					sv.memA += occupiedMem;
				}else{
					sv.cpuB += occupiedCpu;
					sv.memB += occupiedMem;
				}
			}
			//temp_dep_infos.erase(vmId);//暂时不删，不然做编号映射时会出问题。最后统一删除部署信息
			//svRunVmsNumber[svId]--;
			vector<string> &VMIDS=svRunVms[svId];
			VMIDS.erase(remove(VMIDS.begin(), VMIDS.end(), vmId), VMIDS.end());//没错删除就是这么复杂
		}
	}
	
	vector<string> day_buy_info{""};//保存购买信息
	set<string> diffSvType;//这个东西可以记录买了多少种
	//为了编号映射，好球麻烦哟
	unordered_map<int, Server> server_map;
	unordered_map<int, vector<string>> sv_run_vms_map;
	//unordered_map<int, int> svRunVmsNumber_map;
	unordered_map<int, int> svId_map;
	int ID = old_sv_number;
	for(int i=old_sv_number; i<svResources.size(); i++){
		string svType= svResources[i].type;
		if(diffSvType.find(svType)!=diffSvType.end()) continue;
		int number=1;//每种买了多少
		diffSvType.insert(svType);
		server_map[ID]=svResources[i];
		//svRunVmsNumber_map[ID]=svRunVmsNumber[i];
		sv_run_vms_map[ID]=svRunVms[i];
		svId_map[i]=ID++;
		for(int j=i+1; j<svResources.size(); j++){
			if(svResources[j].type==svType){
				server_map[ID]=svResources[j];
				//svRunVmsNumber_map[ID]=svRunVmsNumber[j];
				sv_run_vms_map[ID]=svRunVms[j];
				svId_map[j]=ID++;
				number++;
			}
		}
		day_buy_info.emplace_back("(" + svType + ", " + to_string(number) + ")\n");
	}
	//存一下每日的购买信息
	day_buy_info[0] = "(purchase, " + to_string(diffSvType.size()) + ")\n";//将购买种类存到数组的首位
	purchase_info.emplace_back(day_buy_info);//存一下每日的购买请求
	
	//根据映射，为svResources和svRunVmsNumber和svRunVms中新增的部分重新赋值。是不是感觉很麻烦，是的
	for(int i=old_sv_number; i<svResources.size(); i++){
		svResources[i]=server_map[i];
		//svRunVmsNumber[i]=svRunVmsNumber_map[i];
		svRunVms[i]=sv_run_vms_map[i];
	}
	
	//使用 svId_map 映射去修改部署信息。并更新到全局部署信息中
	for(auto &pair : temp_dep_infos){
		string vmId = pair.first;
		DeployInfo depInfo = pair.second;
		depInfo[0] = svId_map[depInfo[0]];//修改部署到的服务器 Id
		vmDeployInfos[vmId] = depInfo;//更新到全局变量
	}
}

//快速排序，按照服务器上剩余资源量
void quickSort_svcpumem_down(vector<int> &svIds, int l, int r){
	vector<Server> const &svs = svResources;
	if(l < r){
		int i=l, j=r;
		int x=svIds[l];
		while(i < j){
			while(svs[svIds[j]].rest < svs[x].rest && i<j) j--;
			if(i < j) svIds[i++] = svIds[j];
			while(svs[svIds[i]].rest >= svs[x].rest && i<j) i++;
			if(i < j) svIds[j--] = svIds[i];
		}
		svIds[i] = x;
		quickSort_svcpumem_down(svIds, l, i-1);
		quickSort_svcpumem_down(svIds, i+1, r);
	}
}
int findBestServer(vector<int> const &svIds, DeployInfo const &vmDepInfo, int start=0){
	int index = -1;
	int minRest = ~(1<<(sizeof(int)*8 - 1));
	int isDual = vmDepInfo.size()==3 ? 1 : 0;
	int needCpu=vmDepInfo[1], needMem=vmDepInfo[2];
	int rest = 0;
	if(isDual){//双节点
		for(int i=start; i<svIds.size(); i++){
			Server const &sv = svResources[svIds[i]];
			if(sv.cpuA>=needCpu && sv.cpuB>=needCpu && sv.memA>=needMem && sv.memB>=needMem){
				rest = sv.cpuA+sv.cpuB+sv.memA+sv.memB - 2*(needCpu+needMem);//放入后的剩余资源量 cpu + mem
				if(rest<minRest){
					index = i;
					minRest=rest;
				}
			}
		}
	}else{//单节点
		for(int i=start; i<svIds.size(); i++){
			Server const &sv = svResources[svIds[i]];
			if((sv.cpuA>=needCpu && sv.memA>=needMem) || (sv.cpuB>=needCpu && sv.memB>=needMem)){
				rest = sv.cpuA+sv.cpuB+sv.memA+sv.memB - needCpu - needMem;//放入后的剩余资源量 cpu + mem
				if(rest<minRest){
					index = i;
					minRest=rest;
				}
			}
		}
	}
	return index;
}

void migrate(int day){
	vector<string> day_migrate_info{""};//用来存每日的迁移信息。先加入一个空字符串留给 migrate_num
	int max_migrate_num = vmDeployInfos.size()/200;//当日最大可迁移数量，不超过 max_migrate_num
	int migrate_num = 0;//当日已迁移数量
	
	vector<int> svIds;
	for(int i=0; i<svResources.size(); i++) {
		Server &sv = svResources[i];
		svIds.emplace_back(i);
		sv.rest = sv.cpuA + sv.cpuB + sv.memA + sv.memB;//计算服务器上的剩余资源量
	}
	
	quickSort_svcpumem_down(svIds, 0, svIds.size()-1);//按服务器上的剩余资源量排序

	set<string> temp;
	int continue_false=0;//连续迁移不成功的个数
	
	for(int i=0; i<svIds.size(); i++){//从前往后遍历
		int svId = svIds[i];
		Server &sv = svResources[svId];
		vector<string> const vmIds = svRunVms[svId];//svRunVms[svId];//服务器上的虚拟机们
		for(string const &vmId : vmIds){//遍历每台虚拟机
			if(continue_false==850) goto STOP_MIGRATE;//连续迁移不成功，就不再迁移了
			if(temp.find(vmId)!=temp.end()) continue;//这台虚拟机之前迁移过，就不再迁移了
			DeployInfo &deInfo = vmDeployInfos[vmId];//虚拟机部署信息
			int dual = deInfo.size()==3 ? 1 : 0;
			int occupiedCpu=deInfo[1], occupiedMem=deInfo[2];
			if (migrate_num == max_migrate_num) goto STOP_MIGRATE;//达到最大迁移次数
			int index = findBestServer(svIds, deInfo, i+1);//找到最合适迁移到的服务器
			if(index < 0) {//表示找不到能放得下的可以迁移到的服务器
				continue_false++;
				continue;
			}
			continue_false=0;//重新置零
			temp.emplace(vmId);//记录该虚拟机已迁移过
			int goal_svId = svIds[index];//目标服务器Id
			Server &goal_sv = svResources[goal_svId];//目标服务器，一旦找到就表示肯定能放下
			if(dual){//双节点部署
				sv.cpuA += occupiedCpu;//原服务器资源增加
				sv.cpuB += occupiedCpu;
				sv.memA += occupiedMem;
				sv.memB += occupiedMem;
				//svRunVmsNumber[svId]--;
				vector<string> &VMIDS=svRunVms[svId];
				VMIDS.erase(remove(VMIDS.begin(), VMIDS.end(), vmId), VMIDS.end());//没错删除就是这么复杂
				goal_sv.cpuA -= occupiedCpu;//目标服务器资源减少
				goal_sv.cpuB -= occupiedCpu;
				goal_sv.memA -= occupiedMem;
				goal_sv.memB -= occupiedMem;
				//svRunVmsNumber[goal_svId]++;
				svRunVms[goal_svId].emplace_back(vmId);
				//修改部署信息
				deInfo[0] = goal_svId;
				migrate_num++;//当日已迁移数量 + 1
				day_migrate_info.emplace_back("(" + vmId + ", " + to_string(goal_svId) + ")\n");
				continue;
			}else{//单节点部署
				if(goal_sv.cpuA>=occupiedCpu && goal_sv.memA>=occupiedMem){//A节点能放下
					if(deInfo[3]==0){//原来部署在A节点还是B节点
						sv.cpuA += occupiedCpu;
						sv.memA += occupiedMem;
					}else{
						sv.cpuB += occupiedCpu;
						sv.memB += occupiedMem;
					}
					//svRunVmsNumber[svId]--;
					vector<string> &VMIDS=svRunVms[svId];
					VMIDS.erase(remove(VMIDS.begin(), VMIDS.end(), vmId), VMIDS.end());//没错删除就是这么复杂
					goal_sv.cpuA -= occupiedCpu;
					goal_sv.memA -= occupiedMem;
					//svRunVmsNumber[goal_svId]++;
					svRunVms[goal_svId].emplace_back(vmId);
					//修改部署信息
					deInfo[0] = goal_svId;
					deInfo[3] = 0;
					migrate_num++;//当日已迁移数量 + 1
					day_migrate_info.emplace_back("(" + vmId + ", " + to_string(goal_svId) + ", A)\n");
					continue;
				}
				if(goal_sv.cpuB>=occupiedCpu && goal_sv.memB>=occupiedMem){//B节点能放下
					if(deInfo[3]==0){//原来部署在A节点还是B节点
						sv.cpuA += occupiedCpu;
						sv.memA += occupiedMem;
					}else{
						sv.cpuB += occupiedCpu;
						sv.memB += occupiedMem;
					}
					//svRunVmsNumber[svId]--;
					vector<string> &VMIDS=svRunVms[svId];
					VMIDS.erase(remove(VMIDS.begin(), VMIDS.end(), vmId), VMIDS.end());//没错删除就是这么复杂
					goal_sv.cpuB -= occupiedCpu;
					goal_sv.memB -= occupiedMem;
					//svRunVmsNumber[goal_svId]++;
					svRunVms[goal_svId].emplace_back(vmId);
					//修改部署信息
					deInfo[0] = goal_svId;
					deInfo[3] = 1;
					migrate_num++;//当日已迁移数量 + 1
					day_migrate_info.emplace_back("(" + vmId + ", " + to_string(goal_svId) + ", B)\n");
					continue;
				}
			}
		}
	}
	
STOP_MIGRATE:
//	if(day==0 || day%10==0){
//		cout<<day<<" --> "<<max_migrate_num<<" --> "<<migrate_num<<endl;
//	}
	day_migrate_info[0] = "(migration, " + to_string(migrate_num) + ")\n";//将migrate_num转化成字符串放到数组的首位
	migrate_info.emplace_back(day_migrate_info);//存一下每日的迁移信息
}

//处理每日请求
void handleOneDayRequests(int day){
	vector<Request> sortedReqs = daysReqs[day];//复制一份数据，保持原数据不变
	segmentSort(sortedReqs);//分段排序
	
	migrate(day);
	
	//能放的就放，放不下的就记录下来，稍后购买。（该记录中可能含有del，主要是可能有该天添加，该天删除的虚拟机）
	vector<Request> cantHoldReqs;
	for(Request const &req:sortedReqs){
		string vmId=req.vmId;
		if(req.type=="add"){//添加请求
			int svId = findBestServer(svResources, req);
			if(svId < 0){//已买的服务器中放不下该虚拟机
				cantHoldReqs.emplace_back(req);
			}else{//能放下
				int isDual = req.isDual;
				int needCpu = isDual ? req.vmCpu/2 : req.vmCpu;
				int needMem = isDual ? req.vmMem/2 : req.vmMem;
				Server &sv = svResources[svId];//涉及到修改资源量了
				if(isDual){//双节点部署
					sv.cpuA -= needCpu;
					sv.cpuB -= needCpu;
					sv.memA -= needMem;
					sv.memB -= needMem;
					vmDeployInfos[vmId] = DeployInfo{svId, needCpu, needMem};
					//svRunVmsNumber[svId]++;
					svRunVms[svId].emplace_back(vmId);
				}else{//单节点部署
					if(sv.cpuA >= sv.cpuB){//A节点剩得多
						if(sv.cpuA>=needCpu && sv.memA>=needMem){//并且A节点能放下
							sv.cpuA -= needCpu;
							sv.memA -= needMem;
							vmDeployInfos[vmId] = DeployInfo{svId, needCpu, needMem, 0};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
						if(sv.cpuB>=needCpu && sv.memB>=needMem){//虽然A节点剩得多，但是A节点放不下，那么看B节点能不能放下
							sv.cpuB -= needCpu;
							sv.memB -= needMem;
							vmDeployInfos[vmId] = DeployInfo{svId, needCpu, needMem, 1};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
					}else{//B节点剩得多
						if(sv.cpuB>=needCpu && sv.memB>=needMem){//并且B节点能放下
							sv.cpuB -= needCpu;
							sv.memB -= needMem;
							vmDeployInfos[vmId] = DeployInfo{svId, needCpu, needMem, 1};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
						if(sv.cpuA>=needCpu && sv.memA>=needMem){//虽然B节点剩得多，但是B节点放不下，那么看A节点能不能放下
							sv.cpuA -= needCpu;
							sv.memA -= needMem;
							vmDeployInfos[vmId] = DeployInfo{svId, needCpu, needMem, 0};
							//svRunVmsNumber[svId]++;
							svRunVms[svId].emplace_back(vmId);
							continue;
						}
					}
				}
			}
		}else{//删除请求
			if(vmDeployInfos.find(vmId) == vmDeployInfos.end()){//该虚拟机是本应该当天部署的，但是没部署上，被存起来了
				cantHoldReqs.emplace_back(req);//那么当天对该虚拟机的删除也需要存起来。保持相对处理位置不变
				continue;
			}
			DeployInfo vmDeInfo = vmDeployInfos[vmId];
			int svId=vmDeInfo[0], occupiedCpu=vmDeInfo[1], occupiedMem=vmDeInfo[2];//获取部署时的关键信息
			Server &sv=svResources[svId];//涉及到修改资源量了
			if(vmDeInfo.size() == 3){//之前是双节点部署的
				sv.cpuA += occupiedCpu;
				sv.cpuB += occupiedCpu;
				sv.memA += occupiedMem;
				sv.memB += occupiedMem;
			}else{//之前是单节点部署的
				if(vmDeInfo[3] == 0){//之前是部署在A节点上
					sv.cpuA += occupiedCpu;
					sv.memA += occupiedMem;
				}else{
					sv.cpuB += occupiedCpu;
					sv.memB += occupiedMem;
				}
			}
			//vmDeployInfos.erase(vmId);//暂时不删，不然做编号映射时会出问题。最后统一删除部署信息
			//svRunVmsNumber[svId]--;
			vector<string> &VMIDS=svRunVms[svId];
			VMIDS.erase(remove(VMIDS.begin(), VMIDS.end(), vmId), VMIDS.end());//没错删除就是这么复杂
		}
	}
	
	//考虑处理前面放不下的请求
	int old_sv_number = svResources.size();//先记录一下原来已购服务器数量，下面的操作会改变 svResources
	buyServersForReqs(cantHoldReqs);//买服务器，放请求，并做好映射，更新全局部署信息
	
	
	vector<string> day_deploy_info;//保存部署信息
	for(Request const &req : daysReqs[day]){//顺序重新遍历当日请求
		if(req.type=="add"){//添加请求
			string vmId=req.vmId;
			DeployInfo depInfo = vmDeployInfos[vmId];//得到部署信息
			string svId = to_string(depInfo[0]);
			if(depInfo.size()==3){
				day_deploy_info.emplace_back("(" + svId + ")\n");
			}else{
				string nodeInfo = depInfo[3]==0 ? "A" : "B";
				day_deploy_info.emplace_back("(" + svId + ", " + nodeInfo + ")\n");
			}
		}else{//删除请求没有任何输出
			vmDeployInfos.erase(req.vmId);//但是在这里统一删除，需要删除的部署信息。我简直的太机智了
		}
	}
	deploy_info.emplace_back(day_deploy_info);//存一下每日的部署请求
}

//打印输出结果
void print(){
	for(int i=0; i<purchase_info.size(); i++){//遍历每天
		for(string &info:purchase_info[i]){//每天购买
			cout<<info;
		}
		for(string &info:migrate_info[i]){//每天迁移
			cout<<info;
		}
		for(string &info:deploy_info[i]){//每天部署
			cout<<info;
		}
	}
}

//计算每日的耗电成本
//void computePowerCost(){
//	for(int i=0; i<svRunVmsNumber.size(); i++){
//        if(svRunVmsNumber[i] > 0){
//            POWERCOST += svResources[i].powerCost;
//        }
//    }
//}

void cloudResourceSchedulingAlgorithm(){
	readServerAndVmInfos();//读取服务器和虚拟机信息
	int reqDays=0, dayReqNumber=0;
	//一次读入所有的请求
	scanf("%d", &reqDays);
	for (int day=0; day<reqDays; day++){
		scanf("%d", &dayReqNumber);
		readDayRequests(day, dayReqNumber);
	}
	//处理每日请求
	for(int day=0; day<reqDays; day++){
		handleOneDayRequests(day);
		//computePowerCost();
		//if(day==0 || day%50==0) printf("Finished requests of day : %d\n", day);
	}
	print();//打印输出结果
}

int main(){
//	freopen(OUTPUT_REDIRECTION, "w", stdout);
//	clock_t start, finish;
//	
//	//第一份文件
//	start = clock();
//	freopen(INPUT_REDIRECTION_1, "r", stdin);
	cloudResourceSchedulingAlgorithm();
//	finish = clock();
//	TOTALCOST = SERVERCOST + POWERCOST;//总成本
//	SC += SERVERCOST, PC += POWERCOST, TC += TOTALCOST;
//	printf("\nCompute Time: %f s \n", double(finish-start)/CLOCKS_PER_SEC);
//	printf("Server Cost: %lld \nPower Cost: %lld \nTotal Cost: %lld \n", SERVERCOST, POWERCOST, TOTALCOST);
//	
//	
//	//变量清零
//	svInfos.clear();
//	vmInfos.clear();
//	sortedServers.clear();
//	daysReqs.clear();
//	svResources.clear();
//	vmDeployInfos.clear();
//	//svRunVmsNumber.clear();
//	svRunVms.clear();
//	purchase_info.clear();
//	migrate_info.clear();
//	deploy_info.clear();
//	SERVERCOST=0;
//	POWERCOST=0;
//	TOTALCOST=0;
//	
//	
//	//第二份文件
//	start = clock();
//	freopen(INPUT_REDIRECTION_2, "r", stdin);
//	cloudResourceSchedulingAlgorithm();
//	finish = clock();
//	TOTALCOST = SERVERCOST + POWERCOST;//总成本
//	SC += SERVERCOST, PC += POWERCOST, TC += TOTALCOST;
//	printf("\nCompute Time: %f s \n", double(finish-start)/CLOCKS_PER_SEC);
//	printf("Server Cost: %lld \nPower Cost: %lld \nTotal Cost: %lld \n", SERVERCOST, POWERCOST, TOTALCOST);
//	
//	//打印两份文件的总成本
//	printf("\nServer Cost: %lld \nPower Cost: %lld \nTotal Cost: %lld \n", SC, PC, TC);
	return 0;
}

